#pragma once
#include<iostream>
#include<assert.h>
#include<vector>
#include<math.h>
#include<unordered_map>
#include<thread>
#include<mutex>
#include<windows.h>

using std::cout;
using std::cin;
using std::endl;



static const size_t MAX_BYTES = 256 * 1024; // ThreadCache 最大字节数
static const size_t NFREELISTS = 208; // ThreadCache hash桶个数
static const size_t NPAGES = 128; // Page页的个数
static const size_t PAGE_SHIFT = 13; // Page页的个数


// 申请多少页内存
inline static void* SystemAlloc(size_t kpage)
{
	void* ptr = VirtualAlloc(0, kpage << PAGE_SHIFT, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
	if (ptr == nullptr)
		throw std::bad_alloc();
	return ptr;
}

//释放内存
inline static void SystemFree(void* ptr)
{
	VirtualFree(ptr, 0, MEM_RELEASE);
}


//用于管理span页表下标大小
#ifdef _WIN64
typedef unsigned long long PAGE_ID;
#else
typedef size_t PAGE_ID;
#endif


// 使用静态函数，避免一些重定义问题
static void*& Next(void* cur)
{
	return *(void**)cur;
}


// 自由链表管理定长的内存块
class  FreeList
{

public:
	void Push(void* obj)
	{
		assert(obj);
		//头插
		Next(obj) = _freeList;
		_freeList = obj;

		_size++;
	}

	void PushRange(void* start,void* end,int n)
	{
		assert(start && end);
		Next(end) = _freeList;
		_freeList = start;

		_size += n;
	}

	void PopRange(void*& start, void*& end,int n)
	{
		_size -= n;
		end=start = _freeList;
		for (int i = 0; i < n - 1; i++)
			end = Next(end);

		_freeList = Next(end);
		Next(end) = nullptr;
	}

	void* Pop()
	{
		assert(_freeList);

		// 头删
		void* ret = _freeList;
		_freeList = Next(_freeList);

		_size--;
		return ret;
	}

	bool Empty()
	{
		return _freeList == nullptr;
	}


	size_t& MaxSize()
	{
		return _maxSize;
	}
	size_t Size()
	{
		return _size;
	}
private:

	void* _freeList=nullptr; // 自由链表，用来管理定长内存

	size_t _maxSize = 1; // 慢开始使用

	size_t _size = 0;// 自由链表中有多少个对象
};


class SizeClass
{
public:
	//控制整体10%左右内碎片的浪费
	// [1,128]					8byte对齐		 freelist[0,16) 16
	// [128+1,1024]				16byte对齐		 freelist[16,72) 56
	// [1024+1,8*1024]			128byte对齐		 freelist[72,128) 56
	// [8*1024+1,64*1024]       1024byte对齐	 freelist[128,184) 56
	// [64*1024+1,256*1024]     8*1024byte对齐   freelist[184,208) 24

	static inline size_t _Index(size_t bytes, size_t align_shift)
	{
		//return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
		return bytes / (1 << align_shift) - (bytes % (1 << align_shift) == 0);
	}

	// 计算是那个hash桶
	static inline size_t Index(size_t bytes)
	{
		assert(bytes <= MAX_BYTES);

		static int nums[] = { 16,72,128,184,208 };// 每次计算的偏移量
		if (bytes <= 128)
		{

			return _Index(bytes, 3);
		}
		else if (bytes <= 1024)
		{
			return _Index(bytes - 128, 4) + nums[0];
		}
		else if (bytes <= 1024*8)
		{
			return _Index(bytes - 1024, 7) + nums[1];
		}
		else if (bytes <= 1024*64)
		{
			return _Index(bytes - 1024*8, 10) + nums[2];
		}
		else if (bytes <= 1024*256)
		{
			return _Index(bytes - 1024*64, 13) + nums[3];
		}

		return -1;
	}
	

	static inline size_t _RoundUp(size_t bytes, size_t align)
	{
		return (bytes / align - (bytes % align == 0) + 1) * align;
	}

	// 对⻬后分配的内存大小计算
	static inline size_t RoundUp(size_t bytes)
	{
		static int nums[] = { 128,1024,8 * 1024,64 * 1024 };

		if (bytes <= 128) {
			return _RoundUp(bytes, 8);
		}
		else if (bytes <= 1024) {
			return  _RoundUp(bytes-128, 16)+nums[0];
		}
		else if (bytes <= 8*1024) {
			return  _RoundUp(bytes-1024, 128) + nums[1];
		}
		else if (bytes <= 64 * 1024) {
			return  _RoundUp(bytes-8*1024, 1024) + nums[2];
		}
		else if (bytes <= 256 * 1024) {
			return  _RoundUp(bytes-64*1024, 8 * 1024) + nums[3];
		}
		else {
			//return _RoundUp(bytes, 1 << PAGE_SHIFT);
		}

		return -1;
	}

	// 一次向CentralCache最多获取多少个对象值
	static size_t NumMoveSize(size_t size)
	{
		if (size == 0)
			return 0;
		// [2, 512] ⼀次批量移动多少个对象的

		int num = MAX_BYTES / size;
		num = max(2, num);
		num = min(512, num);

		return num;
	}

	// 计算一次向PageCache索要多少个页，最少一页
	static size_t NumMovePage(size_t size)
	{
		size_t num = NumMoveSize(size);
		size_t npage = num * size;
		npage >>= PAGE_SHIFT;
		if (npage == 0)
			npage = 1;
		return npage;
	}

};




struct span
{
	PAGE_ID _pageId=-1;//页表起始号码
	size_t _length=-1;// 多少页

	struct span* next=nullptr;// 链表指针，用于管理
	struct span* prev=nullptr;

	size_t _objSize = 0;	// 对象的切分后大小

	int _useCount=0;		//使用了多少个

	void* _freeList=nullptr;// 用于管理返回的内存块

	bool _isUse = false; // 当前span是否被使用 ，不用_useCount避免切的时候被合并
	                     // 避免旧信息的影响，idToSpan
};



//带头双向循环链表 
class SpanList
{
public:
	SpanList()
	{
		_head = new span;

		_head->next = _head;
		_head->prev = _head;
	}

	struct span* Begin()
	{
		return _head->next;
	}

	struct span* End()
	{
		return _head;
	}

	struct span* PopFront()
	{
		assert(_head->next != _head);

		struct span* ret = Begin();
		Erase(Begin());
		return ret;
	}

	void PushFront(struct span* newSpan)
	{
		Insert(Begin(), newSpan);
	}

	bool Empty()
	{
		return _head->next == _head;
	}

	void Erase(struct span* pos)
	{
		// 不释放对应空间，交给下一次管理
		assert(pos);
		assert(pos != _head);
		assert(!(pos->next == pos));      // 避免自环节点

		//pos->prev->next = pos->next;
		//pos->next->prev = pos->prev;
		struct span* prev = pos->prev;
		struct span* next = pos->next;

		prev->next = next;
		next->prev = prev;
		pos->next = pos->prev = nullptr;// 避免野指针 
	}

	// 在pos位置插入新span，pos往后元素向后移动
	void Insert(struct span* pos, struct span* newNode)
	{
		assert(pos);
		struct span* prev = pos->prev;
		newNode->prev = prev;
		newNode->next = pos;

		prev->next = newNode;
		pos->prev = newNode;
	}

private:
	struct span* _head;
public:
	std::mutex _mutex;// 加锁保护多个进程竞争同一个桶的情况
};




//// 测试代码使用，验证正确性
//class SizeClass2
//{
//public:
//	static inline size_t _Index(size_t bytes, size_t align_shift)
//	{
//		return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
//	}
//
//	// 计算是那个hash桶
//	static inline size_t Index(size_t bytes)
//	{
//		assert(bytes <= MAX_BYTES);
//
//		static int nums[] = { 16,72,128,184,208 };// 每次计算的偏移量
//		if (bytes <= 128)
//		{
//			return _Index(bytes, 3);
//		}
//		else if (bytes <= 1024)
//		{
//			return _Index(bytes - 128, 4) + nums[0];
//		}
//		else if (bytes <= 1024 * 8)
//		{
//			return _Index(bytes - 1024, 7) + nums[1];
//		}
//		else if (bytes <= 1024 * 64)
//		{
//			return _Index(bytes - 1024 * 8, 10) + nums[2];
//		}
//		else if (bytes <= 1024 * 256)
//		{
//			return _Index(bytes - 1024 * 64, 13) + nums[3];
//		}
//
//		return -1;
//	}
//
//
//	static inline size_t _RoundUp(size_t bytes, size_t align)
//	{
//		return (((bytes)+align - 1) & ~(align - 1));
//	}
//
//	// 对⻬后分配的内存大小计算
//	static inline size_t RoundUp(size_t bytes)
//	{
//		if (bytes <= 128) {
//			return _RoundUp(bytes, 8);
//		}
//		else if (bytes <= 1024) {
//			return  _RoundUp(bytes, 16);
//		}
//		else if (bytes <= 8*1024) {
//			return  _RoundUp(bytes, 128);
//		}
//		else if (bytes <= 64 * 1024) {
//			return  _RoundUp(bytes, 1024);
//		}
//		else if (bytes <= 256*1024) {
//			return  _RoundUp(bytes, 8 * 1024);
//		}
//		else {
//			//return _RoundUp(bytes, 1 << PAGE_SHIFT);
//		}
//
//		return -1;
//	}
//private:
//};
//
